package com.example.algorithm.service.impl;

import com.example.algorithm.service.MultiDimensionDynamicPlanService;
import org.springframework.stereotype.Service;

import java.util.Arrays;

/**
 * @author Administrator
 * @date 2024/8/14 19:04
 * @description 多维动态规划
 * 解题思路
 *1、确定dp数组以及下标含义
 * dp[i][j]：表示从（0,0）出发，到（i,j）有dp[i][j]条不同的路径
 * 2、确定递推公式
 * dp[i][j] = dp[i-1][j] + dp[i][j-1]
 * 3、dp数组的初始化
 * 如何初始化，dp[i][0]一定都是1，因为从（0,0）到（0,i）的路径只有一条，dp[0][j]同理：
 *
 *
 */
@Service
public class MultiDimensionDynamicPlanServiceImpl implements MultiDimensionDynamicPlanService {

    /**NO.88 不同路径
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
     *
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
     *
     * 问总共有多少条不同的路径？
     * 解法一：动态规划(二维)
     *解法二：动态规划(一维滚动数组)
     * 解法三：组合数学
     *
     * @param m
     * @param n
     * @return
     */

    /**
     * 动态规划(二维)
     *思路：我们用 f(i,j) 表示从左上角走到 (i,j) 的路径数量，其中 i 和 j 的范围分别是 [0,m) 和 [0,n)。
     * 时间复杂度：O(n*m)，其中 n 是数组长度。只需要对数组遍历一次。
     * 空间复杂度：O(n*m)。
     *
     * @param m
     * @param n
     * @return
     */
    @Override
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int j=0;j<n;j++){
            dp[0][j]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }

    /**
     *动态规划(一维)
     * 思路：
     * 由于 f(i,j) 仅与第 i 行和第 i−1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组
     * 时间复杂度：O(n*m)，其中 n 是数组长度。只需要对数组遍历一次。
     * 空间复杂度：O(n)。
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths1(int m, int n){
        int[] dp= new int[n];
        Arrays.fill(dp,1);
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[j]=dp[j]+dp[j-1];
            }
        }
        return dp[n-1];
    }

    /**
     * 组合数学
     * 思路：
     * 从左上角到右下角的过程中，我们需要移动 m+n−2 次，
     * 其中有 m−1 次向下移动，n−1 次向右移动。因此路径的总数，
     * 就等于从 m+n−2 次移动中选择 m−1 次向下移动的方案数
     *C = (m+n-2)!/(m-1)!*(n-1)!
     * 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
     * 空间复杂度：O(1)。
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths2(int m, int n){
        int ans = 1;
        for(int x=n,y=1;y<m;++x,++y){
            ans = ans*x/y;
        }
        return ans;
    }

    /**NO.89 最小路径和
     * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
     *
     * 说明：每次只能向下或者向右移动一步。
     * @param grid
     * @return
     * 解法一：动态规划(二维)
     */
    /**解法一：动态规划(二维)
     * 思路：创建二维数组 dp，与原始网格的大小相同，dp[i][j] 表示从左上角出发到 (i,j) 位置的最小路径和。显然，dp[0][0]=grid[0][0]。对于 dp 中的其余元素，通过以下状态转移方程计算元素值。
     *
     * 当 i>0 且 j=0 时，dp[i][0]=dp[i−1][0]+grid[i][0]。
     *
     * 当 i=0 且 j>0 时，dp[0][j]=dp[0][j−1]+grid[0][j]。
     *
     * 当 i>0 且 j>0 时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]。
     * 时间复杂度：O(n*m)，其中 n 是数组长度。只需要对数组遍历一次。
     * 空间复杂度：O(n*m)。
     * @param grid
     * @return
     */


    @Override
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        for(int i=1;i<row;i++){
            grid[i][0]+=grid[i-1][0];
        }
        for(int j=1;j<col;j++){
            grid[0][j]+=grid[0][j-1];
        }
        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                grid[i][j]+=Math.min(grid[i][j-1],grid[i-1][j]);
            }
        }
        return grid[row-1][col-1];
    }

    /**NO.90 最长回文子串
     * 给你一个字符串 s，找到 s 中最长的
     * 回文子串
     *
     * @param s
     * @return
     * 解法一：动态规划(二维)
     * 解法二：中心扩展算法
     * 解法三：Manacher 算法
     * 解法四：辅助空间法
     */
    /**
     * 解法一：动态规划(二维)
     * 思路：
     * 对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，
     * 它仍然是个回文串。例如对于字符串 “ababa”，
     * 如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是 “a”
     * 1)只有 s[i+1:j−1] 是回文串，并且 s 的第 i 和 j 个字母相同时，s[i:j] 才会是回文串
     * 2)对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串
     * 时间复杂度：O(n*n)，其中 n 是数组长度。只需要对数组遍历一次。
     * 空间复杂度：O(n*n)。
     * @param s
     * @return
     */

    @Override
    public String longestPalindrome(String s) {
        if(s.length()<2){
            return s;
        }
        boolean[][] dp = new boolean[s.length()][s.length()];
        //初始化
        for(boolean[] dps:dp){
            Arrays.fill(dps,false);
        }
        int result = 0;
        String res = null;
        for(int i=s.length()-1;i>=0;i--){
            for(int j=i;j<s.length();j++){
                //只有 s[i+1:j−1] 是回文串，并且 s 的第 i 和 j 个字母相同时，s[i:j] 才会是回文串
                if(s.charAt(i)==s.charAt(j)&&(j-i<=1||dp[i+1][j-1])){
                        dp[i][j]=true;
                        //获取最大长度
                        result = Math.max(result,j-i);
                       if(j-i>=result){
                        res =s.substring(i,j+1);
                       }
                }

            }
        }
        return res;
    }

    /**
     * 解法二：中心扩展算法
     * 思路：
     * 所有的状态在转移的时候的可能性都是唯一的
     * 边界情况即为子串长度为 1 或 2 的情况。
     * 我们枚举每一种边界情况，并从对应的子串开始不断地向两边扩展。如果两边的字母相同，
     * 我们就可以继续扩展，例如从 P(i+1,j−1) 扩展到 P(i,j)；
     * 如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了
     *时间复杂度：O(n*n)，其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n−1 个，每个回文中心最多会向外扩展 O(n) 次。
     * 空间复杂度：O(1)。
     * @param s
     * @return
     */
    public String longestPalindrome1(String s){
      if(s==null||s.length()==0){
          return "";
      }
      int start=0,end=0;
      for(int i=0;i<s.length();i++){
          int len1=aroundExpand(s,i,i);
          int len2=aroundExpand(s,i,i+1);
          int len = Math.max(len1,len2);
          while (len>end-start){
              start = i-(len-1)/2;
              end = i+len/2;

          }

      }
      return s.substring(start,end+1);
    }


    /**
     * 扩展长度
     * @param s
     * @param left
     * @param right
     * @return
     */
    public int aroundExpand(String s,int left,int right){
        while (left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        return right-left+1;
    }

    /**
     * 解法三：Manacher 算法
     * 思路：
     * ，我们定义一个新概念臂长，表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 2 * length + 1 ，其臂长为 length
     *
     *
     *
     * @param s
     * @return
     */
    public String longestPalindrome2(String s){
        StringBuffer sb = new StringBuffer();
        sb.append("#");
        char [] tmp = s.toCharArray();
        for(char c: tmp){
            sb.append(c);
            sb.append("#");
        }
        sb.append("#");
        String ns = sb.toString();
        int [] res = new int[sb.length()];
        int mid=0,radius=0;
        for(int i=1;i<sb.length()-1;i++){
            int mirror =2*mid-i;
            int arm=0;
            if(radius>i){
                res[i]=Math.min(radius-i,res[mirror]);
            }else{
                res[i]=0;
            }
            // 碰到之前讲的三种情况时候，需要利用中心扩展法
            while (ns.charAt(i + 1 + res[i]) == ns.charAt(i - 1 - res[i])) {
                res[i]++;
            }
            // 判断是否需要更新 R
            if (i + res[i] > radius) {
                mid = i;
                radius = i +res[i];
            }

        }
        // 找出 P 的最大值
        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 1; i < sb.length() - 1; i++) {
            if (res[i] > maxLen) {
                maxLen = res[i];
                centerIndex = i;
            }
        }
        int start = (centerIndex - maxLen) / 2; //最开始讲的求原字符串下标
        return s.substring(start, start + maxLen);

    }



    /**NO.91 最长公共子序列
     * 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
     *
     * 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
     *
     * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
     * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
     * @param text1
     * @param text2
     * @return
     * 解法一：动态规划(二维)
     * 解法二：动态规划(一维)
     *
     */
    @Override
    public int longestCommonSubsequence(String text1, String text2) {
        if(text1.length()==0||text2.length()==0){
            return 0;
        }
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        for(int i=1;i<=text1.length();i++){
            for(int j=1;j<=text2.length();j++){
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]= dp[i-1][j-1]+1;
                }else{
                    dp[i][j]= Math.max(dp[i][j-1],dp[i-1][j]);
                }

            }

        }
        return dp[text1.length()][text2.length()];
    }

    /**NO.92 编辑距离
     * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
     *
     * 你可以对一个单词进行如下三种操作：
     *
     * 插入一个字符
     * 删除一个字符
     * 替换一个字符
     * @param word1
     * @param word2
     * @return
     解法一：动态规划(二维)
    解法二：动态规划(一维)
     */
    @Override
    public int minDistance(String word1, String word2) {
        if(word1.length()==0&&word2.length()==0){
            return 0;
        }
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        for (int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= word2.length(); j++) {
            dp[0][j] = j;
        }
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]= dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1 ;
                }

            }

        }
        return dp[word1.length()][word2.length()];
    }
}
